package com.aqie.easy.hash;

/**
 * 409 最长回文串
 */
public class LongestPalindrome {
    /**
     * 1, 贪心算法 O(N) 3ms
     * @param s
     * @return
     */
    public static int longestPalindrome(String s) {
        int[] count = new int[128];
        for (char c: s.toCharArray())
            count[c]++;

        int ans = 0;
        for (int v: count) {
            ans += v / 2 * 2;
            if (v % 2 == 1 && ans % 2 == 0)
                ans++;
        }
        return ans;
    }

    /**
     * 2, 3ms
     * @param s
     * @return
     */
    public int longestPalindrome2(String s) {
        int[] count = new int[128];
        int max = 0;
        //计算重复的个数
        for(char c: s.toCharArray()){
            if (++count[c] == 2){
                max ++;
                count[c] = 0;
            }
        }
        max *= 2;
        return max < s.length() ? ++max : max;
    }

    public static void main(String[] args) {
        String s = "abccccdd";
        System.out.println(longestPalindrome(s));
    }
}
